package com.le.medium.class1;

import org.junit.Test;

/**
 * 一个完整的括号字符串定义规则如下:
 *  ①空字符串是完整的。
 *  ②如果s是完整的字符串，那么(s)也是完整的。
 *  ③如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
 *  例如，"(()())", ""和"(())()"是完整的括号字符串，
 *  "())(", "()(" 和 ")" 是不完整的括号字符串。
 *  牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化 为一个完整的括号字符串。
 *  请问牛牛至少需要添加多少个括号。
 */
public class Problem07_NeedParentheses {

    // 遇到左括号count++,遇到右括号count--,第一次来到0的位置,则说明需要添加括号
    public static int needParentheses(String str){
        int count = 0;
        int res = 0; // 添加括号记录
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '('){
                count++;
            }else {
                if (count == 0){
                    res++;
                }else {
                    count--;
                }
            }
        }
        return res + count;
    }

    @Test
    public void test(){
        String str = "(()()";
        System.out.println(needParentheses(str));
    }
}
